package gold.digger;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1104 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<Integer> pathInZigZagTree(int label) {
            List<Integer> res = new ArrayList<>();
            res.add(label);
            int level = getLevel(label);
            boolean isNormalLine = level % 2 != 0;
            label = isNormalLine ? (label / 2) : ((int) (Math.pow(2, level - 1)) + (int) (Math.pow(2, level)) - 1 - label) / 2;

            while (label > 0) {
                isNormalLine = !isNormalLine;
                --level;
                if (isNormalLine) {
                    res.add(label);
                } else {
                    // 当前line需要找到其翻转后的真实对应数字
                    int lineLeft = (int) (Math.pow(2, level - 1)), lineRight = (int) (Math.pow(2, level)) - 1;
                    int realLabel = lineRight + lineLeft - label;
                    res.add(realLabel);
                }
                label /= 2;
            }

            Collections.reverse(res);
            return res;
        }

        public int getLevel(int num) {
            for (int i = 31; i >= 0; i--) {
                int re = (num & (1 << i));
                if (re > 0) return i + 1;
            }

            return 1;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.pathInZigZagTree(26));
    }

    public static void main(String[] args) throws Exception {
        LC1104 an = new LC1104();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
